package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1690. 石子游戏 VII
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/6 14:50
 */
public class StoneGameVII {

    public static void main(String[] args) {
        StoneGameVII test = new StoneGameVII();

        // 6
        int[] arr = {5,3,1,4,2};

        // 122
//        int[] arr = { 7,90,5,1,100,10,10,2};

        int i = test.stoneGameVII(arr);
        System.out.println(i);

    }

    public int stoneGameVII(int[] stones) {
        int length = stones.length;
        int[] arr = new int[length + 1];
        arr[1] = stones[0];
        for (int i = 1; i < length; i++) {
            arr[i + 1] = arr[ i] + stones[i];
        }
        int[] items = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int end = j + length - i;
                items[end] = Math.max(arr[end + 1] - arr[j + 1] - items[end], arr[end] - arr[j] - items[end - 1]);
            }
        }
        return items[length - 1];
    }

    public int stoneGameVII2(int[] stones) {
        int length = stones.length;
        int[] arr = new int[length + 1];
        arr[1] = stones[0];
        for (int i = 1; i < length; i++) {
            arr[i + 1] = arr[ i] + stones[i];
        }
        int[][] items = new int[length][length];
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int end = j + length - i;
                items[j][end] = Math.max(arr[end + 1] - arr[j + 1] - items[j + 1][end], arr[end] - arr[j] - items[j][end - 1]);
            }
        }
        return items[0][length - 1];
    }

}
